// Package str
/*

方法1：滑动窗口
时间复杂度：O()
空间复杂度：O()

case1:

r:

滑动窗口技巧-窗口左右边界指针移动，通过双层循环控制:
1.外层循环每次将r向右移动一格
for l, r := 0, 0; r < len(s); r++ {
}

2.内层循环控制l的移动
for check() && l <= r {
	xxxx
	l++
}

需要注意的问题：
1.初始化，如果是求最小，则初始化为最大math.MaxInt32
如果是最大，初始化为最小math.MinInt32

2.遍历字符串的问题
统计字符串中每个字符出现的次数(如果字符均为英文字符则使用byte，否则使用rune), 定义map[byte]int
使用range遍历t，v是int32类型，不能直接用map[byte]int进行统计（int32和byte类型不是同一个类型，byte类型底层是uint8）;
但是通过索引取出来的字符是uint8类型, 所以可以通过m[t[i]]进行统计
m := map[byte]int{}
for i, v := range t {
	m[]
}

*/
package str

func minWindow(s string, t string) string {
	if s == "" || t == "" {
		return ""
	}
	m, cnt := map[byte]int{}, map[byte]int{}
	// 统计t中所有字母出现的次数
	for i, _ := range t {
		m[t[i]] += 1
	}

	// 判断窗口内字符串是否符合条件
	check := func() bool {
		for i, _ := range t {
			if cnt[t[i]] < m[t[i]] {
				return false
			}
		}
		return true
	}

	// 滑动窗口，通过两个指针记录窗口的左右边界，每次移动先统计窗口内各字母数量，然后与m进行比对
	// 如果m中的字母在cnt中均存在且cnt中该字母数量>=m中该字母数量，则说明该窗口符合条件
	minLen := 0
	resL, resR := 0, 0
	for l, r := 0, 0; l < len(s) && r < len(s); r++ {
		if _, ok := m[s[r]]; ok {
			cnt[s[r]] += 1
		}
		if check() {
			newLen := r - l + 1
			if newLen < minLen {
				minLen = newLen
				resL, resR = l, r
			}
			if _, ok := m[s[l]]; ok {
				cnt[s[l]] -= 1
			}
			l++
		}
	}
	return s[resL:resR]
}
